# ===----------------------------------------------------------------------=== #
# Copyright (c) 2025, Modular Inc. All rights reserved.
#
# Licensed under the Apache License v2.0 with LLVM Exceptions:
# https://llvm.org/LICENSE.txt
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.
# ===----------------------------------------------------------------------=== #
"""Implements sort for a limited subset of sizes using sorting network.

The sort network is adapted for the ones found in https://bertdobbelaere.github.io/sorting_networks.html
"""


fn _networks(n: Int) -> List[List[Tuple[Int, Int]]]:
    # fmt: off
    if n == 2:
        return [[(0, 1)]]

    if n == 3:
        return [
                [(0, 2)],
                [(0, 1)],
                [(1, 2)]
            ]

    if n == 4:
        return [
                [(0, 2), (1, 3)],
                [(0, 1), (2, 3)],
                [(1, 2)]
            ]

    if n == 5:
        return [
                [(0, 3), (1, 4)],
                [(0, 2), (1, 3)],
                [(0, 1), (2, 4)],
                [(1, 2), (3, 4)],
                [(2, 3)]
            ]

    if n == 6:
        return [
                [(0, 5), (1, 3), (2, 4)],
                [(1, 2), (3, 4)],
                [(0, 3), (2, 5)],
                [(0, 1), (2, 3), (4, 5)],
                [(1, 2), (3, 4)]
            ]

    if n == 7:
        return [
                [(0, 6), (2, 3), (4, 5)],
                [(0, 2), (1, 4), (3, 6)],
                [(0, 1), (2, 5), (3, 4)],
                [(1, 2), (4, 6)],
                [(2, 3), (4, 5)],
                [(1, 2), (3, 4), (5, 6)]
            ]

    if n == 8:
        return [
                [(0, 2), (1, 3), (4, 6), (5, 7)],
                [(0, 4), (1, 5), (2, 6), (3, 7)],
                [(0, 1), (2, 3), (4, 5), (6, 7)],
                [(2, 4), (3, 5)],
                [(1, 4), (3, 6)],
                [(1, 2), (3, 4), (5, 6)]
            ]

    if n == 9:
        return [
                [(0, 3), (1, 7), (2, 5), (4, 8)],
                [(0, 7), (2, 4), (3, 8), (5, 6)],
                [(0, 2), (1, 3), (4, 5), (7, 8)],
                [(1, 4), (3, 6), (5, 7)],
                [(0, 1), (2, 4), (3, 5), (6, 8)],
                [(2, 3), (4, 5), (6, 7)],
                [(1, 2), (3, 4), (5, 6)]
            ]

    if n == 10:
        return [
                [(0, 8), (1, 9), (2, 7), (3, 5), (4, 6)],
                [(0, 2), (1, 4), (5, 8), (7, 9)],
                [(0, 3), (2, 4), (5, 7), (6, 9)],
                [(0, 1), (3, 6), (8, 9)],
                [(1, 5), (2, 3), (4, 8), (6, 7)],
                [(1, 2), (3, 5), (4, 6), (7, 8)],
                [(2, 3), (4, 5), (6, 7)],
                [(3, 4), (5, 6)]
            ]

    if n == 11:
        return [
                [(0, 9), (1, 6), (2, 4), (3, 7), (5, 8)],
                [(0, 1), (3, 5), (4, 10), (6, 9), (7, 8)],
                [(1, 3), (2, 5), (4, 7), (8, 10)],
                [(0, 4), (1, 2), (3, 7), (5, 9), (6, 8)],
                [(0, 1), (2, 6), (4, 5), (7, 8), (9, 10)],
                [(2, 4), (3, 6), (5, 7), (8, 9)],
                [(1, 2), (3, 4), (5, 6), (7, 8)],
                [(2, 3), (4, 5), (6, 7)]
            ]

    if n == 12:
        return [
                [(0, 8), (1, 7), (2, 6), (3, 11), (4, 10), (5, 9)],
                [(0, 1), (2, 5), (3, 4), (6, 9), (7, 8), (10, 11)],
                [(0, 2), (1, 6), (5, 10), (9, 11)],
                [(0, 3), (1, 2), (4, 6), (5, 7), (8, 11), (9, 10)],
                [(1, 4), (3, 5), (6, 8), (7, 10)],
                [(1, 3), (2, 5), (6, 9), (8, 10)],
                [(2, 3), (4, 5), (6, 7), (8, 9)],
                [(4, 6), (5, 7)],
                [(3, 4), (5, 6), (7, 8)]
            ]

    if n == 13:
        return [
                [(0, 12), (1, 10), (2, 9), (3, 7), (5, 11), (6, 8)],
                [(1, 6), (2, 3), (4, 11), (7, 9), (8, 10)],
                [(0, 4), (1, 2), (3, 6), (7, 8), (9, 10), (11, 12)],
                [(4, 6), (5, 9), (8, 11), (10, 12)],
                [(0, 5), (3, 8), (4, 7), (6, 11), (9, 10)],
                [(0, 1), (2, 5), (6, 9), (7, 8), (10, 11)],
                [(1, 3), (2, 4), (5, 6), (9, 10)],
                [(1, 2), (3, 4), (5, 7), (6, 8)],
                [(2, 3), (4, 5), (6, 7), (8, 9)],
                [(3, 4), (5, 6)]
            ]

    if n == 14:
        return [
                [(0, 1), (2, 3), (4, 5), (6, 7), (8, 9), (10, 11), (12, 13)],
                [(0, 2), (1, 3), (4, 8), (5, 9), (10, 12), (11, 13)],
                [(0, 4), (1, 2), (3, 7), (5, 8), (6, 10), (9, 13), (11, 12)],
                [(0, 6), (1, 5), (3, 9), (4, 10), (7, 13), (8, 12)],
                [(2, 10), (3, 11), (4, 6), (7, 9)],
                [(1, 3), (2, 8), (5, 11), (6, 7), (10, 12)],
                [(1, 4), (2, 6), (3, 5), (7, 11), (8, 10), (9, 12)],
                [(2, 4), (3, 6), (5, 8), (7, 10), (9, 11)],
                [(3, 4), (5, 6), (7, 8), (9, 10)],
                [(6, 7)]
            ]

    if n == 15:
        return [
                [(1, 2), (3, 10), (4, 14), (5, 8), (6, 13), (7, 12), (9, 11)],
                [(0, 14), (1, 5), (2, 8), (3, 7), (6, 9), (10, 12), (11, 13)],
                [(0, 7), (1, 6), (2, 9), (4, 10), (5, 11), (8, 13), (12, 14)],
                [(0, 6), (2, 4), (3, 5), (7, 11), (8, 10), (9, 12), (13, 14)],
                [(0, 3), (1, 2), (4, 7), (5, 9), (6, 8), (10, 11), (12, 13)],
                [(0, 1), (2, 3), (4, 6), (7, 9), (10, 12), (11, 13)],
                [(1, 2), (3, 5), (8, 10), (11, 12)],
                [(3, 4), (5, 6), (7, 8), (9, 10)],
                [(2, 3), (4, 5), (6, 7), (8, 9), (10, 11)],
                [(5, 6), (7, 8)]
            ]

    if n == 16:
        return [
                [(0, 13), (1, 12), (2, 15), (3, 14), (4, 8), (5, 6), (7, 11), (9, 10)],
                [(0, 5), (1, 7), (2, 9), (3, 4), (6, 13), (8, 14), (10, 15), (11, 12)],
                [(0, 1), (2, 3), (4, 5), (6, 8), (7, 9), (10, 11), (12, 13), (14, 15)],
                [(0, 2), (1, 3), (4, 10), (5, 11), (6, 7), (8, 9), (12, 14), (13, 15)],
                [(1, 2), (3, 12), (4, 6), (5, 7), (8, 10), (9, 11), (13, 14)],
                [(1, 4), (2, 6), (5, 8), (7, 10), (9, 13), (11, 14)],
                [(2, 4), (3, 6), (9, 12), (11, 13)],
                [(3, 5), (6, 8), (7, 9), (10, 12)],
                [(3, 4), (5, 6), (7, 8), (9, 10), (11, 12)],
                [(6, 7), (8, 9)]
            ]

    if n == 17:
        return [
                [(0, 11), (1, 15), (2, 10), (3, 5), (4, 6), (8, 12), (9, 16), (13, 14)],
                [(0, 6), (1, 13), (2, 8), (4, 14), (5, 15), (7, 11)],
                [(0, 8), (3, 7), (4, 9), (6, 16), (10, 11), (12, 14)],
                [(0, 2), (1, 4), (5, 6), (7, 13), (8, 9), (10, 12), (11, 14), (15, 16)],
                [(0, 3), (2, 5), (6, 11), (7, 10), (9, 13), (12, 15), (14, 16)],
                [(0, 1), (3, 4), (5, 10), (6, 9), (7, 8), (11, 15), (13, 14)],
                [(1, 2), (3, 7), (4, 8), (6, 12), (11, 13), (14, 15)],
                [(1, 3), (2, 7), (4, 5), (9, 11), (10, 12), (13, 14)],
                [(2, 3), (4, 6), (5, 7), (8, 10)],
                [(3, 4), (6, 8), (7, 9), (10, 12)],
                [(5, 6), (7, 8), (9, 10), (11, 12)],
                [(4, 5), (6, 7), (8, 9), (10, 11), (12, 13)]
            ]

    if n == 18:
        return [
                [(0, 1), (2, 3), (4, 5), (6, 7), (8, 9), (10, 11), (12, 13), (14, 15), (16, 17)],
                [(0, 2), (1, 3), (4, 12), (5, 13), (6, 8), (9, 11), (14, 16), (15, 17)],
                [(0, 14), (1, 16), (2, 15), (3, 17)],
                [(0, 6), (1, 10), (2, 9), (7, 16), (8, 15), (11, 17)],
                [(1, 4), (3, 9), (5, 7), (8, 14), (10, 12), (13, 16)],
                [(0, 1), (2, 5), (3, 13), (4, 14), (7, 9), (8, 10), (12, 15), (16, 17)],
                [(1, 2), (3, 5), (4, 6), (11, 13), (12, 14), (15, 16)],
                [(4, 8), (5, 12), (6, 10), (7, 11), (9, 13)],
                [(1, 4), (2, 8), (3, 6), (5, 7), (9, 15), (10, 12), (11, 14), (13, 16)],
                [(2, 4), (5, 8), (6, 10), (7, 11), (9, 12), (13, 15)],
                [(3, 5), (6, 8), (7, 10), (9, 11), (12, 14)],
                [(3, 4), (5, 6), (7, 8), (9, 10), (11, 12), (13, 14)]
            ]

    if n == 19:
        return [
                [(0, 12), (1, 4), (2, 8), (3, 5), (6, 17), (7, 11), (9, 14), (10, 13), (15, 16)],
                [(0, 2), (1, 7), (3, 6), (4, 11), (5, 17), (8, 12), (10, 15), (13, 16), (14, 18)],
                [(3, 10), (4, 14), (5, 15), (6, 13), (7, 9), (11, 17), (16, 18)],
                [(0, 7), (1, 10), (4, 6), (9, 15), (11, 16), (12, 17), (13, 14)],
                [(0, 3), (2, 6), (5, 7), (8, 11), (12, 16)],
                [(1, 8), (2, 9), (3, 4), (6, 15), (7, 13), (10, 11), (12, 18)],
                [(1, 3), (2, 5), (6, 9), (7, 12), (8, 10), (11, 14), (17, 18)],
                [(0, 1), (2, 3), (4, 8), (6, 10), (9, 12), (14, 15), (16, 17)],
                [(1, 2), (5, 8), (6, 7), (9, 11), (10, 13), (14, 16), (15, 17)],
                [(3, 6), (4, 5), (7, 9), (8, 10), (11, 12), (13, 14), (15, 16)],
                [(3, 4), (5, 6), (7, 8), (9, 10), (11, 13), (12, 14)],
                [(2, 3), (4, 5), (6, 7), (8, 9), (10, 11), (12, 13), (14, 15)]
            ]

    if n == 20:
        return [
                [(0, 3), (1, 7), (2, 5), (4, 8), (6, 9), (10, 13), (11, 15), (12, 18), (14, 17), (16, 19)],
                [(0, 14), (1, 11), (2, 16), (3, 17), (4, 12), (5, 19), (6, 10), (7, 15), (8, 18), (9, 13)],
                [(0, 4), (1, 2), (3, 8), (5, 7), (11, 16), (12, 14), (15, 19), (17, 18)],
                [(1, 6), (2, 12), (3, 5), (4, 11), (7, 17), (8, 15), (13, 18), (14, 16)],
                [(0, 1), (2, 6), (7, 10), (9, 12), (13, 17), (18, 19)],
                [(1, 6), (5, 9), (7, 11), (8, 12), (10, 14), (13, 18)],
                [(3, 5), (4, 7), (8, 10), (9, 11), (12, 15), (14, 16)],
                [(1, 3), (2, 4), (5, 7), (6, 10), (9, 13), (12, 14), (15, 17), (16, 18)],
                [(1, 2), (3, 4), (6, 7), (8, 9), (10, 11), (12, 13), (15, 16), (17, 18)],
                [(2, 3), (4, 6), (5, 8), (7, 9), (10, 12), (11, 14), (13, 15), (16, 17)],
                [(4, 5), (6, 8), (7, 10), (9, 12), (11, 13), (14, 15)],
                [(3, 4), (5, 6), (7, 8), (9, 10), (11, 12), (13, 14), (15, 16)]
            ]

    if n == 21:
        return [
                [(0, 1), (2, 3), (4, 5), (6, 7), (8, 9), (10, 11), (12, 13), (14, 15), (16, 17), (18, 19)],
                [(0, 2), (1, 3), (4, 6), (5, 7), (8, 10), (9, 11), (12, 14), (13, 15), (16, 18), (17, 19)],
                [(0, 8), (1, 9), (2, 10), (3, 11), (4, 12), (5, 13), (6, 14), (7, 15)],
                [(0, 4), (1, 5), (3, 7), (6, 20), (8, 12), (9, 13), (10, 14), (15, 19)],
                [(2, 6), (3, 18), (7, 20)],
                [(2, 16), (3, 6), (5, 18), (7, 17), (11, 20)],
                [(0, 2), (3, 8), (6, 12), (7, 10), (9, 16), (11, 15), (13, 17), (14, 18), (19, 20)],
                [(1, 7), (2, 3), (4, 9), (10, 11), (13, 16), (15, 18), (17, 19)],
                [(1, 4), (5, 10), (6, 13), (7, 8), (11, 14), (12, 16), (15, 17), (18, 19)],
                [(1, 2), (3, 4), (5, 6), (10, 12), (11, 13), (14, 16), (17, 18)],
                [(2, 3), (4, 5), (6, 9), (10, 11), (12, 13), (14, 15), (16, 17)],
                [(6, 7), (8, 9), (15, 16)],
                [(4, 6), (7, 8), (9, 12), (13, 15)],
                [(3, 4), (5, 7), (8, 10), (9, 11), (12, 14)],
                [(5, 6), (7, 8), (9, 10), (11, 12), (13, 14)]
            ]

    if n == 22:
        return [
                [(0, 1), (2, 3), (4, 5), (6, 7), (8, 9), (10, 11), (12, 13), (14, 15), (16, 17), (18, 19), (20, 21)],
                [(0, 2), (1, 3), (4, 6), (5, 7), (8, 12), (9, 13), (14, 16), (15, 17), (18, 20), (19, 21)],
                [(0, 4), (1, 5), (2, 6), (3, 7), (8, 10), (9, 12), (11, 13), (14, 18), (15, 19), (16, 20), (17, 21)],
                [(0, 14), (1, 15), (2, 18), (3, 19), (4, 16), (5, 17), (6, 20), (7, 21), (9, 11), (10, 12)],
                [(2, 8), (3, 11), (6, 9), (10, 18), (12, 15), (13, 19)],
                [(0, 2), (1, 10), (3, 16), (5, 18), (6, 14), (7, 15), (8, 12), (9, 13), (11, 20), (19, 21)],
                [(2, 6), (3, 10), (4, 8), (5, 12), (9, 16), (11, 18), (13, 17), (15, 19)],
                [(1, 4), (7, 13), (8, 14), (9, 12), (17, 20)],
                [(1, 2), (3, 8), (4, 6), (7, 11), (10, 14), (13, 18), (15, 17), (19, 20)],
                [(2, 4), (5, 10), (7, 9), (11, 16), (12, 14), (17, 19)],
                [(5, 6), (7, 8), (9, 11), (10, 12), (13, 14), (15, 16)],
                [(3, 5), (6, 7), (8, 10), (9, 12), (11, 13), (14, 15), (16, 18)],
                [(3, 4), (5, 6), (7, 8), (9, 10), (11, 12), (13, 14), (15, 16), (17, 18)]
            ]

    if n == 23:
        return [
                [(0, 1), (2, 3), (4, 5), (6, 7), (8, 9), (10, 11), (12, 13), (14, 15), (16, 17), (18, 19), (20, 21)],
                [(0, 2), (1, 3), (4, 6), (5, 7), (8, 10), (9, 11), (12, 14), (13, 15), (16, 18), (17, 19), (21, 22)],
                [(0, 4), (1, 5), (2, 6), (3, 7), (8, 12), (9, 13), (10, 14), (11, 15), (17, 21), (18, 20), (19, 22)],
                [(0, 8), (1, 9), (2, 10), (3, 11), (4, 12), (5, 13), (6, 14), (7, 15)],
                [(1, 2), (5, 18), (7, 19), (9, 16), (10, 21), (12, 20), (15, 22)],
                [(5, 9), (6, 7), (10, 18), (11, 21), (12, 17), (13, 20), (14, 15)],
                [(3, 17), (6, 16), (7, 14), (8, 12), (15, 19), (20, 21)],
                [(3, 4), (5, 8), (6, 10), (9, 12), (13, 16), (14, 15), (17, 18), (19, 21)],
                [(0, 5), (1, 8), (2, 12), (3, 9), (4, 10), (7, 13), (11, 17), (14, 16), (18, 20)],
                [(2, 6), (3, 5), (4, 8), (7, 11), (10, 12), (13, 18), (14, 17), (15, 20)],
                [(1, 3), (2, 5), (6, 9), (7, 10), (11, 13), (12, 14), (15, 18), (16, 17), (19, 20)],
                [(2, 3), (4, 6), (8, 9), (11, 12), (13, 14), (15, 16), (17, 19)],
                [(3, 4), (5, 6), (7, 8), (9, 10), (12, 13), (14, 15), (17, 18)],
                [(4, 5), (6, 7), (8, 9), (10, 11), (16, 17)]
            ]

    if n == 24:
        return [
                [(0, 20), (1, 12), (2, 16), (3, 23), (4, 6), (5, 10), (7, 21), (8, 14), (9, 15), (11, 22), (13, 18), (17, 19)],
                [(0, 3), (1, 11), (2, 7), (4, 17), (5, 13), (6, 19), (8, 9), (10, 18), (12, 22), (14, 15), (16, 21), (20, 23)],
                [(0, 1), (2, 4), (3, 12), (5, 8), (6, 9), (7, 10), (11, 20), (13, 16), (14, 17), (15, 18), (19, 21), (22, 23)],
                [(2, 5), (4, 8), (6, 11), (7, 14), (9, 16), (12, 17), (15, 19), (18, 21)],
                [(1, 8), (3, 14), (4, 7), (9, 20), (10, 12), (11, 13), (15, 22), (16, 19)],
                [(0, 7), (1, 5), (3, 4), (6, 11), (8, 15), (9, 14), (10, 13), (12, 17), (16, 23), (18, 22), (19, 20)],
                [(0, 2), (1, 6), (4, 7), (5, 9), (8, 10), (13, 15), (14, 18), (16, 19), (17, 22), (21, 23)],
                [(2, 3), (4, 5), (6, 8), (7, 9), (10, 11), (12, 13), (14, 16), (15, 17), (18, 19), (20, 21)],
                [(1, 2), (3, 6), (4, 10), (7, 8), (9, 11), (12, 14), (13, 19), (15, 16), (17, 20), (21, 22)],
                [(2, 3), (5, 10), (6, 7), (8, 9), (13, 18), (14, 15), (16, 17), (20, 21)],
                [(3, 4), (5, 7), (10, 12), (11, 13), (16, 18), (19, 20)],
                [(4, 6), (8, 10), (9, 12), (11, 14), (13, 15), (17, 19)],
                [(5, 6), (7, 8), (9, 10), (11, 12), (13, 14), (15, 16), (17, 18)]
            ]

    if n == 25:
        return [
                [(0, 1), (2, 3), (4, 5), (6, 7), (8, 9), (10, 11), (12, 13), (14, 15), (16, 17), (18, 19), (20, 21), (22, 23)],
                [(0, 2), (1, 3), (4, 6), (5, 7), (8, 10), (9, 11), (12, 14), (13, 15), (16, 18), (17, 19), (21, 22), (23, 24)],
                [(0, 4), (1, 5), (2, 6), (3, 7), (8, 12), (9, 13), (10, 14), (11, 15), (18, 21), (20, 23), (22, 24)],
                [(0, 8), (1, 9), (2, 10), (3, 11), (4, 12), (5, 13), (6, 14), (7, 15), (16, 20), (17, 22), (19, 24), (21, 23)],
                [(1, 18), (3, 21), (5, 23), (6, 19), (11, 14), (15, 24)],
                [(1, 16), (3, 17), (6, 9), (7, 11), (13, 19), (14, 23)],
                [(0, 1), (2, 16), (3, 8), (7, 20), (10, 13), (11, 22), (15, 23)],
                [(1, 2), (5, 10), (7, 18), (11, 21), (15, 20), (19, 22)],
                [(4, 7), (5, 6), (9, 18), (10, 17), (11, 12), (13, 21), (14, 15), (19, 20), (22, 23)],
                [(3, 4), (7, 8), (9, 10), (11, 16), (12, 17), (13, 18), (19, 21), (20, 22)],
                [(1, 3), (2, 4), (5, 11), (6, 16), (7, 9), (8, 10), (12, 13), (14, 19), (15, 18)],
                [(2, 3), (5, 7), (6, 9), (8, 11), (10, 16), (12, 14), (15, 17)],
                [(3, 5), (4, 6), (7, 8), (9, 11), (10, 12), (13, 14), (15, 16), (17, 18)],
                [(4, 7), (6, 8), (9, 10), (11, 12), (13, 15), (14, 16), (17, 19), (18, 21)],
                [(4, 5), (6, 7), (8, 9), (10, 11), (12, 13), (14, 15), (16, 17), (18, 19), (20, 21)]
            ]

    if n == 26:
        return [
                [(0, 1), (2, 3), (4, 5), (6, 7), (8, 9), (10, 11), (12, 13), (14, 15), (16, 17), (18, 19), (20, 21), (22, 23), (24, 25)],
                [(0, 2), (1, 3), (4, 6), (5, 7), (8, 10), (9, 11), (14, 16), (15, 17), (18, 20), (19, 21), (22, 24), (23, 25)],
                [(0, 4), (1, 6), (2, 5), (3, 7), (8, 14), (9, 16), (10, 15), (11, 17), (18, 22), (19, 24), (20, 23), (21, 25)],
                [(0, 18), (1, 19), (2, 20), (3, 21), (4, 22), (5, 23), (6, 24), (7, 25), (9, 12), (13, 16)],
                [(3, 11), (8, 9), (10, 13), (12, 15), (14, 22), (16, 17)],
                [(0, 8), (1, 9), (2, 14), (6, 12), (7, 15), (10, 18), (11, 23), (13, 19), (16, 24), (17, 25)],
                [(1, 2), (3, 18), (4, 8), (7, 22), (17, 21), (23, 24)],
                [(3, 14), (4, 10), (5, 18), (7, 20), (8, 13), (11, 22), (12, 17), (15, 21)],
                [(1, 4), (5, 6), (7, 9), (8, 10), (15, 17), (16, 18), (19, 20), (21, 24)],
                [(2, 5), (3, 10), (6, 14), (9, 13), (11, 19), (12, 16), (15, 22), (20, 23)],
                [(2, 8), (5, 7), (6, 9), (11, 12), (13, 14), (16, 19), (17, 23), (18, 20)],
                [(2, 4), (3, 5), (6, 11), (7, 10), (9, 16), (12, 13), (14, 19), (15, 18), (20, 22), (21, 23)],
                [(3, 4), (5, 8), (6, 7), (9, 11), (10, 12), (13, 15), (14, 16), (17, 20), (18, 19), (21, 22)],
                [(5, 6), (7, 8), (9, 10), (11, 12), (13, 14), (15, 16), (17, 18), (19, 20)],
                [(4, 5), (6, 7), (8, 9), (10, 11), (12, 13), (14, 15), (16, 17), (18, 19), (20, 21)]
            ]

    if n == 27:
        return [
                [(0, 1), (2, 3), (4, 5), (6, 7), (8, 9), (10, 11), (12, 14), (15, 16), (17, 18), (19, 20), (21, 22), (23, 24), (25, 26)],
                [(0, 2), (1, 3), (4, 6), (5, 7), (8, 10), (9, 11), (12, 13), (15, 17), (16, 18), (19, 21), (20, 22), (23, 25), (24, 26)],
                [(0, 23), (1, 24), (2, 25), (3, 26), (4, 8), (5, 9), (6, 10), (7, 11), (13, 14), (15, 19), (16, 20), (17, 21), (18, 22)],
                [(0, 4), (1, 6), (2, 19), (3, 20), (5, 13), (9, 21), (11, 14), (12, 16), (17, 23), (18, 24), (22, 26)],
                [(5, 17), (6, 16), (7, 22), (9, 25), (10, 24), (12, 15), (13, 20), (14, 26)],
                [(1, 12), (4, 15), (7, 23), (10, 19), (11, 16), (13, 18), (20, 24), (22, 25)],
                [(0, 1), (6, 12), (8, 11), (9, 15), (10, 17), (14, 24), (16, 21), (18, 19)],
                [(1, 4), (2, 8), (3, 11), (12, 15), (14, 20), (16, 22), (21, 25)],
                [(2, 5), (3, 17), (8, 13), (11, 23), (21, 22), (24, 25)],
                [(1, 2), (3, 10), (5, 6), (7, 13), (11, 15), (14, 21), (18, 23), (20, 22)],
                [(4, 5), (6, 9), (7, 8), (13, 17), (14, 16), (19, 23), (22, 24)],
                [(2, 4), (3, 6), (5, 7), (8, 12), (9, 10), (11, 13), (14, 18), (15, 17), (16, 19), (21, 23)],
                [(3, 5), (6, 8), (7, 9), (10, 12), (11, 14), (13, 16), (15, 18), (17, 19), (20, 21), (22, 23)],
                [(5, 6), (8, 11), (9, 10), (12, 14), (13, 15), (17, 18), (19, 21)],
                [(4, 5), (6, 7), (8, 9), (10, 11), (12, 13), (14, 15), (16, 17), (18, 20), (21, 22)],
                [(3, 4), (5, 6), (7, 8), (9, 10), (11, 12), (13, 14), (15, 16), (17, 18), (19, 20)]
            ]

    if n == 28:
        return [
                [(0, 1), (2, 3), (4, 5), (6, 7), (8, 9), (10, 11), (12, 13), (14, 15), (16, 17), (18, 19), (20, 21), (22, 23), (24, 25), (26, 27)],
                [(0, 2), (1, 3), (4, 6), (5, 7), (8, 10), (9, 11), (12, 14), (13, 15), (16, 18), (17, 19), (20, 22), (21, 23), (24, 26), (25, 27)],
                [(0, 4), (1, 5), (2, 6), (3, 7), (8, 12), (9, 13), (14, 18), (15, 19), (20, 24), (21, 25), (22, 26), (23, 27)],
                [(0, 20), (1, 21), (2, 22), (3, 23), (4, 24), (5, 25), (6, 26), (7, 27), (9, 17), (10, 18), (11, 15), (12, 16)],
                [(1, 2), (4, 20), (5, 6), (7, 23), (8, 12), (9, 16), (10, 14), (11, 18), (13, 17), (15, 19), (21, 22), (25, 26)],
                [(0, 8), (1, 9), (2, 12), (3, 5), (4, 10), (6, 16), (7, 13), (11, 21), (14, 20), (15, 25), (17, 23), (18, 26), (19, 27), (22, 24)],
                [(2, 4), (3, 7), (5, 17), (8, 14), (9, 11), (10, 22), (13, 19), (16, 18), (20, 24), (23, 25)],
                [(1, 8), (3, 9), (5, 11), (6, 10), (7, 15), (12, 20), (16, 22), (17, 21), (18, 24), (19, 26)],
                [(1, 2), (4, 6), (5, 9), (10, 16), (11, 17), (12, 14), (13, 15), (18, 22), (21, 23), (25, 26)],
                [(4, 8), (6, 12), (7, 11), (10, 14), (13, 17), (15, 21), (16, 20), (19, 23)],
                [(2, 4), (6, 8), (7, 16), (9, 14), (10, 12), (11, 20), (13, 18), (15, 17), (19, 21), (23, 25)],
                [(3, 10), (5, 12), (7, 9), (11, 13), (14, 16), (15, 22), (17, 24), (18, 20)],
                [(3, 6), (5, 8), (7, 10), (9, 12), (11, 14), (13, 16), (15, 18), (17, 20), (19, 22), (21, 24)],
                [(3, 4), (5, 6), (7, 8), (9, 10), (11, 12), (13, 14), (15, 16), (17, 18), (19, 20), (21, 22), (23, 24)]
            ]

    if n == 29:
        return [
                [(0, 1), (2, 3), (4, 5), (6, 7), (8, 9), (10, 11), (12, 13), (14, 15), (16, 28), (17, 26), (18, 25), (19, 23), (21, 27), (22, 24)],
                [(0, 2), (1, 3), (4, 6), (5, 7), (8, 10), (9, 11), (12, 14), (13, 15), (17, 22), (18, 19), (20, 27), (23, 25), (24, 26)],
                [(0, 4), (1, 5), (2, 6), (3, 7), (8, 12), (9, 13), (10, 14), (11, 15), (16, 20), (17, 18), (19, 22), (23, 24), (25, 26), (27, 28)],
                [(0, 8), (1, 9), (2, 10), (3, 11), (4, 12), (5, 13), (6, 14), (7, 15), (16, 18), (20, 22), (21, 25), (24, 27), (26, 28)],
                [(1, 8), (2, 24), (4, 19), (5, 20), (6, 21), (7, 27), (9, 18), (10, 23), (11, 26), (13, 22), (14, 25), (15, 28), (16, 17)],
                [(0, 6), (2, 4), (3, 24), (5, 10), (12, 19), (13, 18), (14, 21), (15, 25), (20, 23), (26, 27)],
                [(0, 16), (1, 6), (3, 12), (4, 8), (5, 17), (7, 24), (14, 20), (15, 26), (18, 21), (19, 23), (25, 27)],
                [(1, 5), (2, 16), (3, 10), (6, 9), (7, 18), (8, 17), (11, 19), (13, 14), (15, 22), (21, 23), (25, 26)],
                [(1, 2), (3, 5), (4, 8), (6, 16), (7, 11), (9, 17), (10, 12), (14, 20), (15, 18), (19, 24), (22, 27)],
                [(4, 6), (9, 16), (10, 13), (11, 19), (12, 14), (20, 21), (22, 26), (23, 24)],
                [(2, 4), (3, 6), (7, 16), (8, 9), (11, 17), (15, 19), (18, 23), (24, 25)],
                [(3, 4), (5, 9), (7, 10), (11, 13), (12, 16), (14, 17), (15, 20), (19, 21), (22, 24)],
                [(5, 8), (6, 7), (9, 12), (10, 11), (13, 14), (15, 16), (17, 20), (18, 19), (21, 23), (24, 25)],
                [(5, 6), (7, 8), (9, 10), (11, 12), (13, 15), (14, 16), (17, 18), (19, 20), (21, 22)],
                [(4, 5), (6, 7), (8, 9), (10, 11), (12, 13), (14, 15), (16, 17), (18, 19), (20, 21), (22, 23)]
            ]

    if n == 30:
        return [
                [(0, 1), (2, 3), (4, 5), (6, 7), (8, 9), (10, 11), (12, 13), (14, 15), (16, 17), (18, 19), (20, 21), (22, 23), (24, 25), (26, 27), (28, 29)],
                [(0, 2), (1, 3), (4, 6), (5, 7), (8, 10), (9, 11), (13, 15), (14, 16), (18, 20), (19, 21), (22, 24), (23, 25), (26, 28), (27, 29)],
                [(0, 4), (1, 5), (2, 6), (3, 7), (8, 14), (9, 17), (10, 16), (12, 20), (13, 19), (15, 21), (22, 26), (23, 27), (24, 28), (25, 29)],
                [(0, 8), (1, 9), (2, 14), (3, 17), (4, 10), (5, 11), (6, 16), (12, 26), (13, 23), (15, 27), (18, 24), (19, 25), (20, 28), (21, 29)],
                [(1, 13), (2, 12), (3, 15), (4, 18), (5, 19), (6, 20), (7, 21), (8, 22), (9, 23), (10, 24), (11, 25), (14, 26), (16, 28), (17, 27)],
                [(0, 4), (2, 8), (3, 13), (5, 9), (6, 22), (7, 23), (10, 12), (11, 15), (14, 18), (16, 26), (17, 19), (20, 24), (21, 27), (25, 29)],
                [(0, 2), (1, 14), (3, 5), (4, 8), (9, 13), (11, 17), (12, 18), (15, 28), (16, 20), (21, 25), (24, 26), (27, 29)],
                [(2, 4), (5, 9), (6, 14), (7, 13), (8, 10), (15, 23), (16, 22), (19, 21), (20, 24), (25, 27)],
                [(6, 8), (7, 11), (10, 14), (12, 16), (13, 17), (15, 19), (18, 22), (21, 23)],
                [(4, 6), (7, 9), (8, 10), (11, 13), (12, 14), (15, 17), (16, 18), (19, 21), (20, 22), (23, 25)],
                [(1, 8), (3, 18), (5, 20), (7, 22), (9, 24), (10, 12), (11, 26), (13, 15), (14, 16), (17, 19), (21, 28)],
                [(1, 2), (3, 10), (5, 12), (7, 14), (9, 16), (11, 18), (13, 20), (15, 22), (17, 24), (19, 26), (27, 28)],
                [(2, 4), (3, 6), (5, 8), (7, 10), (9, 12), (11, 14), (13, 16), (15, 18), (17, 20), (19, 22), (21, 24), (23, 26), (25, 27)],
                [(3, 4), (5, 6), (7, 8), (9, 10), (11, 12), (13, 14), (15, 16), (17, 18), (19, 20), (21, 22), (23, 24), (25, 26)]
            ]

    if n == 31:
        return [
                [(0, 1), (2, 3), (4, 5), (6, 7), (8, 9), (10, 11), (12, 13), (14, 15), (16, 17), (18, 19), (20, 21), (22, 23), (24, 25), (26, 27), (28, 29)],
                [(0, 2), (1, 3), (4, 6), (5, 7), (8, 10), (9, 11), (12, 14), (13, 15), (16, 18), (17, 19), (20, 22), (21, 23), (24, 26), (25, 27), (28, 30)],
                [(0, 4), (1, 5), (2, 6), (3, 7), (8, 12), (9, 13), (10, 14), (11, 15), (16, 20), (17, 21), (18, 22), (19, 23), (24, 28), (25, 29), (26, 30)],
                [(0, 8), (1, 9), (2, 10), (3, 11), (4, 12), (5, 13), (6, 14), (7, 15), (16, 24), (17, 25), (18, 26), (19, 27), (20, 28), (21, 29), (22, 30)],
                [(0, 16), (1, 8), (2, 4), (3, 12), (5, 10), (6, 9), (7, 14), (11, 13), (17, 24), (18, 20), (19, 28), (21, 26), (22, 25), (23, 30), (27, 29)],
                [(1, 2), (3, 5), (4, 8), (6, 22), (7, 11), (9, 25), (10, 12), (13, 14), (17, 18), (19, 21), (20, 24), (23, 27), (26, 28), (29, 30)],
                [(1, 17), (2, 18), (3, 19), (4, 20), (5, 10), (7, 23), (8, 24), (11, 27), (12, 28), (13, 29), (14, 30), (21, 26)],
                [(3, 17), (4, 16), (5, 21), (6, 18), (7, 9), (8, 20), (10, 26), (11, 23), (13, 25), (14, 28), (15, 27), (22, 24)],
                [(1, 4), (3, 8), (5, 16), (7, 17), (9, 21), (10, 22), (11, 19), (12, 20), (14, 24), (15, 26), (23, 28), (27, 30)],
                [(2, 5), (7, 8), (9, 18), (11, 17), (12, 16), (13, 22), (14, 20), (15, 19), (23, 24), (26, 29)],
                [(2, 4), (6, 12), (9, 16), (10, 11), (13, 17), (14, 18), (15, 22), (19, 25), (20, 21), (27, 29)],
                [(5, 6), (8, 12), (9, 10), (11, 13), (14, 16), (15, 17), (18, 20), (19, 23), (21, 22), (25, 26)],
                [(3, 5), (6, 7), (8, 9), (10, 12), (11, 14), (13, 16), (15, 18), (17, 20), (19, 21), (22, 23), (24, 25), (26, 28)],
                [(3, 4), (5, 6), (7, 8), (9, 10), (11, 12), (13, 14), (15, 16), (17, 18), (19, 20), (21, 22), (23, 24), (25, 26), (27, 28)]
            ]

    if n == 32:
        return [
                [(0, 1), (2, 3), (4, 5), (6, 7), (8, 9), (10, 11), (12, 13), (14, 15), (16, 17), (18, 19), (20, 21), (22, 23), (24, 25), (26, 27), (28, 29), (30, 31)],
                [(0, 2), (1, 3), (4, 6), (5, 7), (8, 10), (9, 11), (12, 14), (13, 15), (16, 18), (17, 19), (20, 22), (21, 23), (24, 26), (25, 27), (28, 30), (29, 31)],
                [(0, 4), (1, 5), (2, 6), (3, 7), (8, 12), (9, 13), (10, 14), (11, 15), (16, 20), (17, 21), (18, 22), (19, 23), (24, 28), (25, 29), (26, 30), (27, 31)],
                [(0, 8), (1, 9), (2, 10), (3, 11), (4, 12), (5, 13), (6, 14), (7, 15), (16, 24), (17, 25), (18, 26), (19, 27), (20, 28), (21, 29), (22, 30), (23, 31)],
                [(0, 16), (1, 8), (2, 4), (3, 12), (5, 10), (6, 9), (7, 14), (11, 13), (15, 31), (17, 24), (18, 20), (19, 28), (21, 26), (22, 25), (23, 30), (27, 29)],
                [(1, 2), (3, 5), (4, 8), (6, 22), (7, 11), (9, 25), (10, 12), (13, 14), (17, 18), (19, 21), (20, 24), (23, 27), (26, 28), (29, 30)],
                [(1, 17), (2, 18), (3, 19), (4, 20), (5, 10), (7, 23), (8, 24), (11, 27), (12, 28), (13, 29), (14, 30), (21, 26)],
                [(3, 17), (4, 16), (5, 21), (6, 18), (7, 9), (8, 20), (10, 26), (11, 23), (13, 25), (14, 28), (15, 27), (22, 24)],
                [(1, 4), (3, 8), (5, 16), (7, 17), (9, 21), (10, 22), (11, 19), (12, 20), (14, 24), (15, 26), (23, 28), (27, 30)],
                [(2, 5), (7, 8), (9, 18), (11, 17), (12, 16), (13, 22), (14, 20), (15, 19), (23, 24), (26, 29)],
                [(2, 4), (6, 12), (9, 16), (10, 11), (13, 17), (14, 18), (15, 22), (19, 25), (20, 21), (27, 29)],
                [(5, 6), (8, 12), (9, 10), (11, 13), (14, 16), (15, 17), (18, 20), (19, 23), (21, 22), (25, 26)],
                [(3, 5), (6, 7), (8, 9), (10, 12), (11, 14), (13, 16), (15, 18), (17, 20), (19, 21), (22, 23), (24, 25), (26, 28)],
                [(3, 4), (5, 6), (7, 8), (9, 10), (11, 12), (13, 14), (15, 16), (17, 18), (19, 20), (21, 22), (23, 24), (25, 26), (27, 28)]
            ]

    if n == 64:
        return [
                [(0, 2), (1, 3), (4, 6), (5, 7), (8, 10), (9, 11), (12, 14), (13, 15), (16, 18), (17, 19), (20, 22), (21, 23), (24, 26), (25, 27), (28, 30), (29, 31), (32, 34), (33, 35), (36, 38), (37, 39), (40, 42), (41, 43), (44, 46), (45, 47), (48, 50), (49, 51), (52, 54), (53, 55), (56, 58), (57, 59), (60, 62), (61, 63)],
                [(0, 1), (2, 3), (4, 5), (6, 7), (8, 9), (10, 11), (12, 13), (14, 15), (16, 17), (18, 19), (20, 21), (22, 23), (24, 25), (26, 27), (28, 29), (30, 31), (32, 33), (34, 35), (36, 37), (38, 39), (40, 41), (42, 43), (44, 45), (46, 47), (48, 49), (50, 51), (52, 53), (54, 55), (56, 57), (58, 59), (60, 61), (62, 63)],
                [(0, 52), (1, 2), (3, 55), (4, 48), (5, 6), (7, 51), (8, 60), (9, 10), (11, 63), (12, 56), (13, 14), (15, 59), (16, 32), (17, 18), (19, 35), (20, 24), (21, 22), (23, 27), (25, 26), (28, 44), (29, 30), (31, 47), (33, 34), (36, 40), (37, 38), (39, 43), (41, 42), (45, 46), (49, 50), (53, 54), (57, 58), (61, 62)],
                [(0, 20), (1, 53), (2, 54), (3, 23), (4, 28), (5, 49), (6, 50), (7, 31), (8, 36), (9, 61), (10, 62), (11, 39), (12, 16), (13, 57), (14, 58), (15, 19), (17, 33), (18, 34), (21, 25), (22, 26), (24, 52), (27, 55), (29, 45), (30, 46), (32, 56), (35, 59), (37, 41), (38, 42), (40, 60), (43, 63), (44, 48), (47, 51)],
                [(0, 4), (1, 21), (2, 22), (3, 7), (5, 29), (6, 30), (8, 12), (9, 37), (10, 38), (11, 15), (13, 17), (14, 18), (16, 20), (19, 23), (24, 32), (25, 53), (26, 54), (27, 35), (28, 36), (31, 39), (33, 57), (34, 58), (40, 44), (41, 61), (42, 62), (43, 47), (45, 49), (46, 50), (48, 52), (51, 55), (56, 60), (59, 63)],
                [(0, 8), (1, 5), (2, 6), (3, 11), (4, 12), (7, 15), (9, 13), (10, 14), (16, 40), (17, 21), (18, 22), (19, 43), (20, 44), (23, 47), (24, 28), (25, 33), (26, 34), (27, 31), (29, 37), (30, 38), (32, 36), (35, 39), (41, 45), (42, 46), (48, 56), (49, 53), (50, 54), (51, 59), (52, 60), (55, 63), (57, 61), (58, 62)],
                [(1, 9), (2, 10), (4, 8), (5, 13), (6, 14), (7, 11), (12, 48), (15, 51), (16, 24), (17, 41), (18, 42), (19, 27), (20, 28), (21, 45), (22, 46), (23, 31), (25, 29), (26, 30), (32, 40), (33, 37), (34, 38), (35, 43), (36, 44), (39, 47), (49, 57), (50, 58), (52, 56), (53, 61), (54, 62), (55, 59)],
                [(4, 16), (5, 9), (6, 10), (7, 19), (8, 24), (11, 27), (13, 49), (14, 50), (17, 25), (18, 26), (20, 32), (21, 29), (22, 30), (23, 35), (28, 40), (31, 43), (33, 41), (34, 42), (36, 52), (37, 45), (38, 46), (39, 55), (44, 56), (47, 59), (53, 57), (54, 58)],
                [(1, 4), (5, 17), (6, 18), (8, 16), (9, 25), (10, 26), (11, 19), (12, 24), (15, 27), (21, 33), (22, 34), (29, 41), (30, 42), (36, 48), (37, 53), (38, 54), (39, 51), (44, 52), (45, 57), (46, 58), (47, 55), (59, 62)],
                [(2, 8), (9, 17), (10, 18), (12, 20), (13, 25), (14, 26), (15, 23), (24, 32), (27, 35), (28, 36), (31, 39), (37, 49), (38, 50), (40, 48), (43, 51), (45, 53), (46, 54), (55, 61)],
                [(2, 4), (12, 16), (13, 21), (14, 22), (15, 19), (20, 24), (23, 27), (25, 33), (26, 34), (28, 32), (29, 37), (30, 38), (31, 35), (36, 40), (39, 43), (41, 49), (42, 50), (44, 48), (47, 51), (59, 61)],
                [(4, 16), (5, 20), (10, 40), (13, 17), (14, 18), (21, 25), (22, 26), (23, 53), (24, 28), (27, 31), (29, 33), (30, 34), (32, 36), (35, 39), (37, 41), (38, 42), (43, 58), (45, 49), (46, 50), (47, 59)],
                [(3, 17), (6, 36), (7, 21), (8, 32), (9, 24), (11, 41), (13, 28), (14, 44), (15, 45), (18, 48), (19, 49), (22, 52), (25, 29), (26, 30), (27, 57), (31, 55), (33, 37), (34, 38), (35, 50), (39, 54), (42, 56), (46, 60)],
                [(6, 20), (8, 16), (10, 24), (11, 25), (14, 28), (15, 29), (17, 33), (18, 32), (21, 37), (22, 36), (26, 42), (27, 41), (30, 46), (31, 45), (34, 48), (35, 49), (38, 52), (39, 53), (43, 57), (47, 55)],
                [(3, 18), (5, 8), (6, 12), (7, 22), (15, 21), (17, 32), (19, 33), (23, 37), (26, 40), (30, 44), (31, 46), (41, 56), (42, 48), (45, 60), (51, 57), (55, 58)],
                [(3, 16), (7, 20), (11, 26), (18, 24), (19, 25), (22, 28), (23, 29), (27, 33), (30, 36), (34, 40), (35, 41), (37, 52), (38, 44), (39, 45), (43, 56), (47, 60)],
                [(3, 9), (7, 13), (10, 16), (11, 17), (14, 20), (15, 30), (19, 34), (21, 36), (23, 38), (25, 40), (26, 32), (27, 42), (29, 44), (31, 37), (33, 48), (43, 49), (46, 52), (47, 53), (50, 56), (54, 60)],
                [(3, 8), (7, 10), (9, 12), (11, 18), (13, 14), (15, 24), (17, 22), (19, 28), (21, 26), (23, 25), (27, 34), (29, 36), (30, 32), (31, 33), (35, 44), (37, 42), (38, 40), (39, 48), (41, 46), (45, 52), (49, 50), (51, 54), (53, 56), (55, 60)],
                [(3, 6), (7, 12), (11, 16), (15, 17), (18, 20), (19, 24), (21, 22), (23, 30), (25, 32), (26, 28), (27, 29), (31, 38), (33, 40), (34, 36), (35, 37), (39, 44), (41, 42), (43, 45), (46, 48), (47, 52), (51, 56), (57, 60)],
                [(3, 5), (6, 8), (7, 9), (10, 12), (11, 13), (14, 16), (15, 18), (17, 20), (19, 21), (22, 24), (23, 26), (25, 28), (27, 30), (29, 32), (31, 34), (33, 36), (35, 38), (37, 40), (39, 41), (42, 44), (43, 46), (45, 48), (47, 49), (50, 52), (51, 53), (54, 56), (55, 57), (58, 60)],
                [(3, 4), (7, 8), (11, 12), (13, 14), (15, 16), (17, 18), (19, 20), (21, 22), (23, 24), (25, 26), (27, 28), (29, 30), (31, 32), (33, 34), (35, 36), (37, 38), (39, 40), (41, 42), (43, 44), (45, 46), (47, 48), (49, 50), (51, 52), (55, 56), (59, 60)]
            ]
    # fmt: on

    return [[]]


fn _sort[
    origin: MutOrigin, dtype: DType, //, n: Int
](x: Span[Scalar[dtype], origin]):
    comptime network = _networks(n)

    constrained[
        len(network) > 0, String("a sorting of length ", n, " is not available")
    ]()

    @parameter
    for level in network:

        @parameter
        for r in range(len(level)):
            comptime ij = level[r]
            comptime i = ij[0]
            comptime j = ij[1]
            x[i], x[j] = (x[i], x[j]) if x[i] <= x[j] else (x[j], x[i])
